Non-volatile memories can retain stored data without applying power. Therefore, non-volatile memories have been increasingly used in a variety of host devices. With the development of technology, various non-volatile memory technologies such as NOR flash, NAND flash, resistive random-access memory (hereinafter, ReRAM) and phase change memory (hereinafter, PCM) etc. are proposed.
Blocks in non-volatile memories can tolerate a finite number of program/erase cycles before becoming unreliable. The repeated use of a limited number of blocks in the non-volatile memory can cause a memory device to prematurely wear out or exceed its program endurance. Thus, wear leveling, a process of managing access to non-volatile memory devices, is provided to equalize the use of memory blocks and extend life of the memory device.
In short, the wear leveling algorithms prolong usage of non-volatile memory devices by evenly distributing data in the non-volatile memory device. For each physical block, a practical programming cycle count is monitored and compared with a specific threshold of programming cycle count. Once the practical programming cycle count corresponding to a physical block is equivalent to the specific threshold of programming cycle count, the wear leveling algorithm will perform special operations on the physical block, such as prohibit block accessing. That is to say, selection of the specific threshold of programming cycle count seriously impacts utilization of memory blocks.
In FIGS. 1 and 2, allowable programming cycle counts (i.e. lifetime/endurance) of memory blocks a, b, c, d, and e are represented by the rectangles. The specific threshold of programming cycle count is shown by the dotted lines. The upper edges of the rectangles represent the allowable programming cycle counts of the memory blocks a, b, c, d, and e. A memory block corresponding to a longer rectangle has a longer lifetime, i.e. allowable programming cycle counts of the memory block is greater. When practical programming cycle count of a memory block reaches the specific threshold of programming cycle count as defined by the dotted lines, the wear leveling algorithm no longer programs the memory block.
FIG. 1 is a schematic diagram illustrating a conventional wear leveling algorithm with a conservative approach. According to FIG. 1, the specific threshold of programming cycle count is smaller. That is, position of the dotted line is relatively lower and the practical programming cycle counts of the memory blocks a, b, c, d, and e are less.
The screentone areas corresponding to the memory blocks a, b, c, d, and e, represent differences between their allowable programming cycle counts, and the specific threshold of programming cycle count determined by the wear leveling algorithm. Therefore, the screentone areas indicate part of the allowable programming cycle counts which are not actually utilized. In reality, the screentone areas represent waste of allowable programming cycle counts corresponding to the memory blocks a, b, c, d, and e.
FIG. 2 is a schematic diagram illustrating a conventional wear leveling algorithm with an aggressive approach. According to FIG. 2, the specific threshold of programming cycle count is greater. That is, position of the dotted line is relatively higher and the practical programming cycle counts of the memory blocks a, b, c, d, and e are greater. Compared with FIG. 1, only two screentone areas corresponding to the memory blocks b and c are shown in FIG. 2.
The double headed arrows indicate over-utilization of the memory blocks a, d, and e. That is, the wear leveling algorithm is not aware that the practical programming cycle counts of memory blocks a, d, and e are greater than the allowable programming cycle counts of the same. In such case, data stored in memory blocks a, d, and e might be erroneous. Some error correcting code (hereinafter, ECC) algorithms are applied to remedy such problems. However, correcting capability of ECC algorithms is not unlimited and calculation process of ECC algorithms brings overhead as well.
The conventional wear leveling algorithms are based on a questionable basis, that is, lifetime of different memory blocks are all assumed to be consistent. However, the allowable programming cycle counts of different memory blocks vary in practice. Consequently, determination of the specific threshold of programming cycle count becomes a dilemma.
When the specific threshold of programming cycle count is low, i.e. the wear leveling algorithm is conservative/strict, lifetime of the memory blocks will likely to be highly under estimated. That is to say, the memory device is not effectively utilized.
Alternately, when the specific threshold of programming cycle count is high, i.e. the wear leveling algorithm is aggressive/lenient, lifetime of the memory blocks will likely to be highly overestimated. Such over estimation of endurance of memory blocks implies risk of losing data.
In addition, the conventional wear leveling algorithms require an extra space to store the accumulated cycle counts corresponding to the memory blocks. As memory capacity increases and management unit becomes fine-grained, extra space required by the wear leveling algorithms should not be overlooked.